716B - Complete the Word - CodeForces Solution


greedy two pointers *1300

Please click on ads to support us..

Python Code:

import string, sys

input = lambda: sys.stdin.buffer.readline().decode().strip()
print = sys.stdout.write

s = input()
for i in range(len(s) - 25):
    substring = s[i: i + 26]
    if all(substring.count(char) == 1 for char in substring if char != "?"):
        setsub = set(substring)
        for char in set(string.ascii_uppercase) - setsub:
            substring = substring.replace("?", char, 1)
        s = s[0:i] + substring + s[i + 26:]
        ans = s.replace("?", "A")
        break
else:
    ans = "-1"
print(ans)

C++ Code:

#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define lop(k,n) for(int i=k;i<n;i++)
#define int  long long
#define sz(x) long(x.size())
#define te int t;cin>>t;while(t--)
#define el '\n'
#define pi pair<int,int>

string P="ABCDEFGHIJKLMNOPQRSTUVWXYZ";

void sol(){
string s;cin>>s;
int l=0,r=0;
int n=sz(s);
int ok=0;
string can="";
for(int i=0;i<n;i++){
    string a=s.substr(i,26);
    set<int>st;
    int x=0;
    for(char c : a){
        if(c=='?')x++;
        else st.insert(c);
        }
        if(st.size()+x==26){
            can = a;
            l=i;
            r=i+26;
            ok=1;
        }
        if(ok)break;
}
if(ok){
    string ss = "";
    for(char c : P){
        if(can.find(c)==string ::npos)ss+=c;

    }
    int x=0;
    for(int i=0;i<sz(can);i++){
        if(can[i]=='?'){
            can[i]=ss[x];
            x++;
        }
    }
    string ans =s.substr(0,l)+can+s.substr(r);
    for(int i=0;i<ans.size();i++){
        if(ans[i]=='?'){
            if(!i)ans[i]=P[0];
            else
            ans[i]=ans[i-1];
        }
    }
    cout<<ans;
}
else cout<<-1;
}



int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
sol();
}


Comments

Submit
0 Comments
More Questions

1399A - Remove Smallest
208A - Dubstep
1581A - CQXYM Count Permutations
337A - Puzzles
495A - Digital Counter
796A - Buying A House
67A - Partial Teacher
116A - Tram
1472B - Fair Division
1281C - Cut and Paste
141A - Amusing Joke
112A - Petya and Strings
677A - Vanya and Fence
1621A - Stable Arrangement of Rooks
472A - Design Tutorial Learn from Math
1368A - C+=
450A - Jzzhu and Children
546A - Soldier and Bananas
32B - Borze
1651B - Prove Him Wrong
381A - Sereja and Dima
41A - Translation
1559A - Mocha and Math
832A - Sasha and Sticks
292B - Network Topology
1339A - Filling Diamonds
910A - The Way to Home
617A - Elephant
48A - Rock-paper-scissors
294A - Shaass and Oskols